グラフ理論の分野において、 木 木は秩序の建築的象徴です。複数の経路が同じ目的地に至る混沌としたネットワークとは異なり、木は任意の2点間を一意かつ唯一の経路で結びます。この構造的な制約は制限ではなく、階層システムの基盤であり、ギリシャ神話の系譜から現代のオペレーティングシステムのディレクトリ構造まで広く応用されています。
1. 木の構造
階層が存在する前には、 フリー木という概念があります。その定義はシンプルながらも洗練されています：
定義 9.1.1
（フリー）木 $T$ とは、任意の2頂点 $v$ と $w$ に対して、 一意な単純パス が存在する単純なグラフです。これは、グラフが 連結 かつ 非巡回 （サイクルがない）ことを意味します。
特定の頂点を「原点」として指定すると、 根付き木という木が生成されます。この変換により、関係性が根からの距離と方向によって定義される空間的な方向性が導入されます。
階層的用語集
根が $v_0$ の木において、単純パス $(v_0, v_1, \dots, v_n)$ を考えてみましょう：
- 親: $v_{n-1}$ が $v_n$ の親です。
- 子: $v_n$ は $v_{n-1}$ の子です。
- 兄弟: 同じ親を持つ頂点。
- 先祖: 根から $v_n$ までのパス上のすべての頂点（一部の文脈では $v_n$ 自身は除く）。
- 子孫: $v$ を先祖とするすべての頂点。
構造的指標
- レベル: 根から頂点までの唯一のパスの長さ。根自身は レベル 0に位置します。
- 高さ: 木に含まれる最大のレベル番号。
- 葉（終端頂点）: 子を持たない頂点——枝の終わり。
- 内部（分岐）頂点: 少なくとも1つの子を持つ頂点。
🎯 核心概念：部分木
部分木 は、ある頂点とそのすべての子孫からなる木の部分集合です。ファイルシステムでは、フォルダとその中のすべてのファイル・サブフォルダに相当します。図 9.2.1 では、 is a subset of a tree consisting of a vertex and all its descendants. In a file system, this is a folder and every file/subfolder inside it. In Figure 9.2.1, the lineage of クロノス （ゼウス、ポセイドン、ハデス、アレス）は オーガノスに位置します。
2. 実世界での応用
木は数学的な抽象概念にとどまらず、組織化の基盤です：
- コンピュータのファイルシステム： 'C:' ドライブが根であり、フォルダが内部頂点、ファイルが葉です。
- 経営構造図： CEOが根であり、マネージャーが内部ノード、個人貢献者は葉です。
- 意思決定フレームワーク： 「インスタント・インソニティ」のようなパズルや インスタント・インソニティ あるいは n-立方体の平面性 の分析は、木のような状態空間を探索することにしばしば依存します。